package com.xmg.dataStructure.tensuanfa;

public class KMP {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDC";
        String str2 = "ABCDABD";

        int[] next = kmpNext(str2);
        int i = kmpSearch(str1, str2, next);
        System.out.println(i);

    }
    //kmp搜索算法

    /**
     *
     * @param str1 源字符串
     * @param str2 子串
     * @param next 部分匹配表 子串对应的部分匹配表
     * @return -1 没有匹配到 否则返回第一个位置
     */
    public static int kmpSearch(String str1,String str2,int[] next){

        for(int i=0,j=0;i<str1.length();i++){
            //需要考虑str1.charAt(i) != str2.charAt(j) 的情况
            //kmp核心算法
            while (j>0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j-1];
            }
            if(str1.charAt(i) == str2.charAt(j)){
                j++;
            }

            if(j == str2.length()){
                return i-j+1;
            }
        }
        return -1;
    }

    //获取一个字符串的部分匹配值表
    public static int[] kmpNext(String dest){
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i=1,j=0;i<dest.length();i++){
            //dest.charAt(i)!=dest.charAt(j) 需要从next[j-1]开始找，直到发现dest.charAt(i)==dest.charAt(j)时推出
            while (j>0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j-1];
            }

            //dest.charAt(i)==dest.charAt(j)满足时，部分匹配值+1
            if(dest.charAt(i)==dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    //计算字符串中最长不重复的子串长度
    public int lengthOfLongestSubstring(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }

        return res;
    }
}
